package datastructure.search;

/**
 * Description：折半（二分）查找算法的递归非递归实现
 * Author: zhangc
 * Date：2017/7/24 23:04
 */
public class BinarySearch {

    public static <T extends Comparable<? super T>> int binarySearch(T[] array, T key) {
        return binarySearch(array, 0, array.length - 1, key);
    }

    private static <T extends Comparable<? super T>> int binarySearch(T[] array, int low, int high, T key) {
        int mid = (low + high) >> 1;
        if (array[ low ].compareTo(key) > 0 || array[ high ].compareTo(key) < 0 || low > high)
            return -1;
        if (array[ mid ].equals(key))
            return mid;
        else if (array[ mid ].compareTo(key) < 0)
            return binarySearch(array, mid + 1, high, key);
        else
            return binarySearch(array, low, mid - 1, key);
    }

    public static <T extends Comparable<? super T>> int binarySearchNoRecursive(T[] array, T key) {
        int low = 0;
        int high = array.length - 1;
        int mid;
        while (low <= high) {
            mid = (low + high) >> 1;
            if (array[ mid ].compareTo(key) == 0)
                return mid;
            else if (array[ mid ].compareTo(key) > 0)
                high = mid - 1;
            else low = mid + 1;
        }
        return -1;
    }


    /**
     * 查找第一个 等于 key 的index
     *
     * @param array
     * @param low
     * @param high
     * @param key
     * @param <T>
     * @return
     */
    public static <T extends Comparable<? super T>> int getFirstKIndex(T[] array, int low, int high, T key) {
        if (low > high)
            return -1;
        int mid = (low + high) >> 1;
        if (array[ mid ].equals(key) && (!array[ mid - 1 ].equals(key) || mid == low))
            return mid;
        else if (array[ mid ].compareTo(key) >= 0)
            return getFirstKIndex(array, low, mid - 1, key);
        else return getFirstKIndex(array, mid + 1, high, key);
    }

    /**
     * 查找最后一个 等于Key 的index
     *
     * @param array
     * @param low
     * @param high
     * @param key
     * @param <T>
     * @return
     */
    public static <T extends Comparable<? super T>> int getLastKIndex(T[] array, int low, int high, T key) {
        if (low > high)
            return -1;
        int mid = (low + high) >> 1;
        if (array[ mid ].equals(key) && (!array[ mid + 1 ].equals(key) || mid == high))
            return mid;
        else if (array[ mid ].compareTo(key) > 0)
            return getLastKIndex(array, low, mid - 1, key);
        else return getLastKIndex(array, mid + 1, high, key);
    }
}
